package huawei_nowcoder;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Description: 素数伴侣
 * @Date: 2020/4/21
 * @Author: 许群星
 */
public class _27_PrimePartner {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            //初始输入    奇数和偶数分别存放
            int n=sc.nextInt();
            List<Integer> odds=new ArrayList<>();
            List<Integer> evens=new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int temp=sc.nextInt();
                if ((temp&1)==1)
                    odds.add(temp);
                else
                    evens.add(temp);
            }

            //处理
            int ans=0;
            int[] match=new int[evens.size()];
            for (int i = 0; i < odds.size(); i++) {
                int[] used=new int[evens.size()];
                if (find(odds.get(i),evens,used,match))
                    ans++;
            }
            System.out.println(ans);
        }
        sc.close();
    }
    //查找
    public static boolean find(int x,List<Integer> events,int[] used,int[] match){
        for (int i = 0; i < events.size(); i++) {
            if (isPrime(x+events.get(i))&&used[i]==0){
                used[i]=1;
                if(match[i]==0||find(match[i],events,used,match)){
                    match[i]=x;
                    return true;
                }
            }
        }
        return false;
    }

    //判断是否是素数
    public static boolean isPrime(int num){
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}
/*
题目描述
题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。
现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，
挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，
而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:
有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。

输出:
输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入描述:
输入说明
1 输入一个正偶数n
2 输入n个整数

输出描述:
求得的“最佳方案”组成“素数伴侣”的对数。

示例1
输入
复制
4
2 5 6 13
输出
复制
2
 */